package sort.heap;

import util.Util;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = new int[]{9, 1, 0, 3, 4, 2, 6, 7, 8, 5};
        // int[] arr = Util.generateArray(10);

        Util.print(arr);
        heapSort(arr);
        Util.print(arr);

    }

    /**
     * 升序排序数组
     * 思路：首先计算出最后一个父节点，从最后一个父节点向前循环比较父子节点大小，
     * 如果子节点比父节点大，则交换，直到根节点，即找出最大值，依次循环，
     * 即将数组按升序排序
     * @param arr 要排序的数组
     */
    public static void heapSort(int[] arr) {

        int lastParentNodeIndex = arr.length / 2 - 1;

        for (int i = lastParentNodeIndex; i >= 0; i--) {
            // 从最后一个父节点开始往上调整，循环完成调整成一个大顶堆
            adjustHeap(arr, i, arr.length - 1);
        }

        for (int i = arr.length - 1; i > 0; i--) {
            // 交换堆顶和堆底元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 堆长度减一，再次调整成大顶堆
            adjustHeap(arr, 0, i - 1);

        }
    }

    /**
     * 调整堆方法
     *
     * @param arr   排序数组
     * @param start 要排序的起始下标
     * @param end   要排序的结束下标
     */
    private static void adjustHeap(int[] arr, int start, int end) {
        while (true) {
            // 下标从0开始，start为根节点下标
            // start * 2 + 1为左子节点下标
            // start * 2 + 2为右子节点下标
            int left = start * 2 + 1;
            int right = left + 1;

            // 判断出左右子节点中较大节点下标
            int max = left;
            if (left > end) {
                // 没有子节点，退出循环
                break;
            }
            if (right <= end && arr[left] < arr[right]) {
                // 右子节点存在，且左子节点小于右子节点
                // 记录较大节点下标
                max = right;
            }
            if (arr[max] > arr[start]) {
                // 子节点中较大节点大于父节点，交换父子节点
                int temp = arr[start];
                arr[start] = arr[max];
                arr[max] = temp;
                // 记录较大节点下标
                start = max;
            } else {
                // 父节点大于子节点，退出循环
                break;
            }
        }
    }

}
